package com.ywgt;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * 马踏棋盘
 */
public class HorseChessboard {
    //X轴
    private static int X;
    //Y轴
    private static int Y;
    //棋盘
    private static int [][] chessboard;
    //是否已经走过
    private static boolean[] isVisited;
    private static boolean finished;
    public static void main(String[] args) {
        X=6;
        Y=6;
        chessboard=new int[X][Y];
        isVisited=new boolean[X*Y];
        move(chessboard,0,0,1);
        show();
    }

    /**
     * 移动马
     * @param chessboard
     * @param row
     * @param col
     * @param step
     */
    public static void move(int [][] chessboard,int row,int col,int step){
        //将这个节点先标记第几步
        chessboard[row][col]=step;
        //标记为已走过
        isVisited[row*X+col]=true;
        //根据坐标创建一个点 xy轴方向相反
        Point point=new Point(col,row);
        //根据这个点查询下一步可以前进的点
        ArrayList<Point> next = next(point);
        //使用贪心算法进行排序，每次选择最优的点（后面步数最少的点，可以减少回溯次数，提高效率）
        sort(next);
        //当集合不为空时循环
        while(next.size()>0){
            //取出第一个点
            Point p = next.remove(0);
            //判断是否已经走过了
            if(!isVisited[p.y*X+p.x]){
                //如果没有走过就进行递归调用
                move(chessboard,p.y,p.x,step+1);
            }
        }
        //如果循环结束step还没有达到总步数，说明没有结束或者在回溯上次
        if(step<isVisited.length&&!finished){
            chessboard[row][col]=0; //将当前节点置为0
            isVisited[row*X+col]=false; //将当前位置标记为未走过
        }else {
            finished=true;
        }
    }

    /**
     * 根据当前位置获得下一步可以前进的位置
     * @param point
     * @return
     */
    public static ArrayList<Point> next(Point point){
        ArrayList<Point> ps=new ArrayList<Point>();
        if(point.x-2>=0&&point.y-1>=0){  //向左上方5
            ps.add(new Point(point.x-2, point.y-1));
        }
        if(point.x-1>=0&&point.y-2>=0){  //向左上方6
            ps.add(new Point(point.x-1, point.y-2));
        }

        if(point.x+1<X&&point.y-2>=0){  //向右上方7
            ps.add(new Point(point.x+1,point.y-2));
        }
        if(point.x+2<X&&point.y-1>=0){  //向右上方0
            ps.add(new Point(point.x+2,point.y-1));
        }

        if(point.x-2>=0&&point.y+1<Y){  //向左下方4
            ps.add(new Point(point.x-2,point.y+1));
        }
        if(point.x-1>=0&&point.y+2<Y){  //向左下方3
            ps.add(new Point(point.x-1,point.y+2));
        }

        if(point.x+2<X&&point.y+1<Y){  //向右下方1
            ps.add(new Point(point.x+2,point.y+1));
        }
        if(point.x+1<X&&point.y+2<Y){  //向右下方2
            ps.add(new Point(point.x+1,point.y+2));
        }

        return ps;
    }

    /**
     * 贪心算法，将下次需要走的点进行非降序排序，这样可以减少回溯次数，提高效率
     * @param points
     */
    public static void sort(ArrayList<Point> points){
        points.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                ArrayList<Point> p1 = next(o1);
                ArrayList<Point> p2 = next(o2);
                if(p1.size()>p2.size()){
                    return 1;
                }
                if(p1.size()==p2.size()){
                    return 0;
                }
                else {
                    return -1;
                }
            }
        });
    }

    /**
     * 打印行进线路
     */
    public static  void show(){
        for (int i = 0; i < chessboard.length; i++) {
            for (int j = 0; j < chessboard[i].length; j++) {
                System.out.print(chessboard[i][j]+"\t");
            }
            System.out.println();
        }

    }


}
